package datastructure.LRU;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/31 16:24
 * @description:
 */
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class TimeWheelLRUCache<K, V> {
    // 缓存节点
    static class Node<K, V> {
        K key;
        V value;
        long expireTime; // 过期时间戳(毫秒)
        Node<K, V> prev;
        Node<K, V> next;
        // 时间轮相关
        int bucketIndex; // 所在时间轮桶索引
        long cycle; // 循环次数
        Node<K, V> timeNext; // 时间轮链表中的下一个节点
        Node<K, V> timePrev; // 时间轮链表中的上一个节点

        public Node(K key, V value, long expireTime) {
            this.key = key;
            this.value = value;
            this.expireTime = expireTime;
        }
    }

    // 时间轮配置
    private final int tickMs; // 每个刻度的毫秒数
    private final int wheelSize; // 时间轮大小
    private final long interval; // 时间轮覆盖的总时间(ms) = tickMs * wheelSize
    private final List<Node<K, V>>[] buckets; // 时间轮桶
    private long currentTime; // 当前时间轮指向的时间(ms)
    private final Thread timeWheelThread; // 时间轮驱动线程
    private volatile boolean isRunning; // 时间轮是否运行

    // LRU相关
    private final int capacity; // 缓存容量
    private final Map<K, Node<K, V>> cache; // 哈希表
    private final Node<K, V> head; // LRU链表头(最近最少使用)
    private final Node<K, V> tail; // LRU链表尾(最近使用)
    private final ReentrantLock lock; // 锁保证线程安全

    /**
     * 构造函数
     * @param capacity 缓存容量
     * @param tickMs 时间轮每个刻度的毫秒数
     * @param wheelSize 时间轮大小
     */
    public TimeWheelLRUCache(int capacity, int tickMs, int wheelSize) {
        if (capacity <= 0 || tickMs <= 0 || wheelSize <= 0) {
            throw new IllegalArgumentException("参数必须为正数");
        }

        // LRU初始化
        this.capacity = capacity;
        this.cache = new ConcurrentHashMap<>(capacity);
        this.lock = new ReentrantLock();
        this.head = new Node<>(null, null, 0);
        this.tail = new Node<>(null, null, 0);
        head.next = tail;
        tail.prev = head;

        // 时间轮初始化
        this.tickMs = tickMs;
        this.wheelSize = wheelSize;
        this.interval = (long) tickMs * wheelSize;
        this.buckets = new List[wheelSize];
        for (int i = 0; i < wheelSize; i++) {
            buckets[i] = new LinkedList<>();
        }
        this.currentTime = System.currentTimeMillis() / tickMs * tickMs; // 对齐到最近的刻度

        // 启动时间轮线程
        this.isRunning = true;
        this.timeWheelThread = new Thread(this::timeWheelRun, "TimeWheel-Thread");
        this.timeWheelThread.setDaemon(true);
        this.timeWheelThread.start();
    }

    /**
     * 时间轮驱动方法
     */
    private void timeWheelRun() {
        while (isRunning) {
            try {
                // 等待到下一个刻度
                long sleepTime = currentTime + tickMs - System.currentTimeMillis();
                if (sleepTime > 0) {
                    Thread.sleep(sleepTime);
                }

                lock.lock();
                try {
                    currentTime += tickMs;
                    int index = (int) (currentTime / tickMs % wheelSize);

                    // 处理当前桶中的过期任务
                    List<Node<K, V>> bucket = buckets[index];
                    Iterator<Node<K, V>> iterator = bucket.iterator();

                    while (iterator.hasNext()) {
                        Node<K, V> node = iterator.next();
                        // 处理循环次数为0的节点(已到期)
                        if (node.cycle == 0) {
                            // 从缓存中移除过期节点
                            cache.remove(node.key);
                            removeFromLRU(node);
                            iterator.remove();
                        } else {
                            // 循环次数减1，移到下一轮
                            node.cycle--;
                            moveNodeToNextBucket(node);
                            iterator.remove();
                        }
                    }
                } finally {
                    lock.unlock();
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
                break;
            }
        }
    }

    /**
     * 将节点移到下一个桶
     */
    private void moveNodeToNextBucket(Node<K, V> node) {
        int newIndex = (node.bucketIndex + 1) % wheelSize;
        node.bucketIndex = newIndex;
        buckets[newIndex].add(node);
    }

    /**
     * 从时间轮中移除节点
     */
    private void removeFromTimeWheel(Node<K, V> node) {
        if (node.bucketIndex >= 0 && node.bucketIndex < wheelSize) {
            buckets[node.bucketIndex].remove(node);
        }
    }

    /**
     * 将节点添加到时间轮
     */
    private void addToTimeWheel(Node<K, V> node) {
        long expireTime = node.expireTime;
        if (expireTime <= 0) return; // 永不过期

        long delay = expireTime - currentTime;
        if (delay <= 0) { // 已过期
            return;
        }

        // 计算循环次数和桶索引
        long cycles = delay / interval;
        int bucketIndex = (int) ((currentTime / tickMs + delay / tickMs) % wheelSize);

        node.cycle = cycles;
        node.bucketIndex = bucketIndex;
        buckets[bucketIndex].add(node);
    }

    /**
     * 获取缓存值
     */
    public V get(K key) {
        lock.lock();
        try {
            Node<K, V> node = cache.get(key);
            if (node == null) {
                return null;
            }

            // 检查是否已过期
            if (node.expireTime > 0 && System.currentTimeMillis() > node.expireTime) {
                removeNode(node);
                return null;
            }

            // 移到LRU尾部表示最近使用
            moveToTail(node);
            return node.value;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 添加缓存项
     * @param key 键
     * @param value 值
     * @param expireAfterMillis 过期时间(毫秒)，0表示永不过期
     */
    public void put(K key, V value, long expireAfterMillis) {
        if (expireAfterMillis < 0) {
            throw new IllegalArgumentException("过期时间不能为负数");
        }

        lock.lock();
        try {
            Node<K, V> node = cache.get(key);

            if (node != null) {
                // 已存在，更新值和过期时间
                node.value = value;
                // 先从时间轮移除旧的
                removeFromTimeWheel(node);
                // 更新过期时间
                node.expireTime = expireAfterMillis > 0 ?
                        System.currentTimeMillis() + expireAfterMillis : 0;
                // 添加到时间轮
                addToTimeWheel(node);
                // 移到LRU尾部
                moveToTail(node);
                return;
            }

            // 检查容量，必要时淘汰最近最少使用的节点
            if (cache.size() >= capacity) {
                Node<K, V> leastUsed = head.next;
                removeNode(leastUsed);
            }

            // 创建新节点
            long expireTime = expireAfterMillis > 0 ?
                    System.currentTimeMillis() + expireAfterMillis : 0;
            Node<K, V> newNode = new Node<>(key, value, expireTime);
            cache.put(key, newNode);
            addToTail(newNode);
            addToTimeWheel(newNode);
        } finally {
            lock.unlock();
        }
    }

    /**
     * 移除节点（从缓存、LRU链表和时间轮）
     */
    private void removeNode(Node<K, V> node) {
        cache.remove(node.key);
        removeFromLRU(node);
        removeFromTimeWheel(node);
    }

    /**
     * 从LRU链表中移除节点
     */
    private void removeFromLRU(Node<K, V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 将节点添加到LRU链表尾部
     */
    private void addToTail(Node<K, V> node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    /**
     * 将节点移到LRU链表尾部
     */
    private void moveToTail(Node<K, V> node) {
        removeFromLRU(node);
        addToTail(node);
    }

    /**
     * 关闭缓存，停止时间轮线程
     */
    public void shutdown() {
        isRunning = false;
        timeWheelThread.interrupt();
        try {
            timeWheelThread.join();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    // 测试方法
    public static void main(String[] args) throws InterruptedException {
        // 创建缓存：容量为3，时间轮每个刻度100ms，大小为20（覆盖2秒）
        TimeWheelLRUCache<String, Integer> cache = new TimeWheelLRUCache<>(3, 100, 20);

        // 添加缓存项
        cache.put("a", 1, 500);   // 500ms后过期
        cache.put("b", 2, 1000);  // 1秒后过期
        cache.put("c", 3, 1500);  // 1.5秒后过期

        System.out.println("初始获取: a=" + cache.get("a") + ", b=" + cache.get("b") + ", c=" + cache.get("c"));

        // 添加第四个元素，触发LRU淘汰
        cache.put("d", 4, 2000);  // 2秒后过期
        System.out.println("添加d后获取c: " + cache.get("c"));  // 被淘汰，返回null

        // 等待600ms，a应该过期
        Thread.sleep(600);
        System.out.println("600ms后获取a: " + cache.get("a") + ", b=" + cache.get("b"));

        // 再等待500ms，b应该过期
        Thread.sleep(500);
        System.out.println("再500ms后获取b: " + cache.get("b") + ", d=" + cache.get("d"));

        // 关闭缓存
        cache.shutdown();
    }
}
